import random
import copy
import string


def insert_left_by_list(array, index, index2):
    '''
    将index2位置的元素插入到列表array的index左侧

    :param array:
    :param index:
    :param index2:
    :return:
    '''
    for i in range(index2, index, -1):
        # print(i)
        swap(array, i, i - 1)


def find_small(array, index):
    '''
    向前寻找最后一个比index大的索引值 , 要求index之前的元素已经升序排列
    :param array:
    :param index:
    :return:
    '''
    if index == 0:
        #  列表只有一个值
        return index
    if array[index] > array[index - 1]:
        #  或者 当前值是最大的
        return index
    for i in range(index, -1, -1):
        # print(i)
        # print(f'[{index}],[{i}]:{array[index]},{array[i]}')
        if array[index] > array[i]:
            return i + 1
    return i


def swap(arr, i1, i2):
    arr[i1], arr[i2] = arr[i2], arr[i1]


def check(arr, order='ascend'):
    '''
    列表排序对数器
    :param arr: 列表
    :param order: 降序descend 升序ascend
    :return: boolean
    '''
    size = len(arr)
    arr_sorted = copy.deepcopy(arr)
    arr_sorted.sort()
    for i in range(size):
        if arr[i] != arr_sorted[i]:
            print(f'false at {i}: {arr[i]}')
            return False
        # if order == 'ascend':
        #     if i + 1 < size and arr[i] > arr[i + 1]:
        #         print(f'false at {i}: {arr[i]}')
        #         return False
        # else:
        #     if i + 1 < size and arr[i] < arr[i + 1]:
        #         print(f'false at {i}: {arr[i]}')
        #         return False
    return True


def sjlb(chang=10, min_num=0, max_num=20):
    """返回随机列表"""
    a = random.randint(1, chang)
    lb = []
    for i in range(a):
        b = random.randint(min_num, max_num)
        lb.append(b)
    # print(lb)
    return lb


def check_all(f, times, _type='int'):
    """
    多次验证排序正确性
    :rtype: object
    :param f: 排序函数名
    :param times: 验证次数
    :param _type: 列表类型: 整型'int', 字符串'str'
    :return: True or False
    """
    for _ in range(times):
        # create a random list
        # randint(low,high,size,dtype)
        lb = []
        if _type == 'int':
            # lb = numpy.random.randint(-1000, 1000, size=10)
            lb = sjlb(100, -10000, 10000)
        else:
            for i in range(100):
                letters = ''.join(random.sample(string.ascii_letters + string.digits, random.randint(1, 20)))
                lb.append(letters)
        t_lb = f(lb) # 调用排序函数, 并获取返回值
        if type(t_lb) is list:
            # if 返回值是列表 将排好序的列表赋值给原表
            lb = t_lb
        # print(lb)
        if not check(lb):
            print(f'{_}th',lb)
            return False
    return True


if __name__ == '__main__':
    # l = [0, 13, 17, 0]
    # insert_by_list(l, 0, 1)
    # print(l)
    l = [1, 2, 3, 4]  # 3
    l = [1, 2, 5, 3]  # 1
    l = [6, 7, 8, 3]  # 0
    l = [13, 13, 15, 8]  # 0
    l = [8, 13, 11]  # 0
    # print(find_small(l, len(l) - 1))
    # insert_left_by_list(l, 1, 2)
    # print(l)
    check_all(max, 10, 'str')
    # print(sjlb(1000, -1000, 10000))
